package com.lun.medium;


import java.util.LinkedList;

import com.lun.util.BinaryTree.TreeNode;

public class MaximumBinaryTree {
	//方法一：
    public TreeNode constructMaximumBinaryTree(int[] nums) {
    	return constructMaximumBinaryTree(nums, 0, nums.length - 1);
    }
    
    private TreeNode constructMaximumBinaryTree(int[] nums, int start, int end) {
    	int maxValueIndex = findMax(nums, start, end);
    	if(maxValueIndex == -1) return null;
    	
    	return new TreeNode(nums[maxValueIndex], //
    			constructMaximumBinaryTree(nums, start, maxValueIndex - 1), //
    			constructMaximumBinaryTree(nums, maxValueIndex + 1, end));
    }
    
    private int findMax(int[] nums, int start, int end) {
    	if(start > end) return -1;
    	int maxValueIndex = start;
    	for(int i = start + 1; i <= end; i++) {
    		if(nums[i] > nums[maxValueIndex])
    			maxValueIndex = i;
    	}
    	return maxValueIndex;
    }
    
    //方法二：
    public TreeNode constructMaximumBinaryTree2(int[] nums) {
    	LinkedList<TreeNode> stack = new LinkedList<>();
        for(int i = 0; i < nums.length; i++) {
            TreeNode curr = new TreeNode(nums[i]);
            while(!stack.isEmpty() && stack.peek().val < nums[i]) {
                curr.left = stack.pop();
            }
            if(!stack.isEmpty()) {
                stack.peek().right = curr;
            }
            stack.push(curr);
        }
        
        return stack.isEmpty() ? null : stack.removeLast();
    }
    
}
